package challenge.计挑赛._2020国赛Java3;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 设有一个小写英文字母(a - z)组成的字符串，现在定义其满足如下性质的最短子串，
 * 即该最短子串包含这个字符串中出现过的所有字母。现在请你输出最左边的该类子串。
 * 输入说明
 * 一行，为待处理字串(长度≤200)
 * 输出说明
 * 一行，为满足条件的子串。
 * 输入样例复制
 * abbcba
 * 输出样例复制
 * cba
 * 数据范围提示
 *
 * 思路：
 * hash 双指针
 * @since 2022 - 12 - 15 - 9:30
 */
//双指针
class Main_2{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        //hash 记录出现的字母种类
        int[] hash = new int[26];
        for(char c : s.toCharArray()) {
            hash[c - 'a'] = 1;
        }
        //记录出现的字母种类
        int cnt = 0;
        for(int i = 0; i < 26; i++) if(hash[i] == 1) cnt++;
        //双指针
        int l = 0, r = 0;
        int minL = 0, minLen = Integer.MAX_VALUE;
        while(r < s.length()) {
            //区间 [l, r]
            //添加 s[r]
            hash[s.charAt(r) - 'a']--;
            //这种情况包含了一个新的字母
            if(hash[s.charAt(r) - 'a'] == 0) cnt--;
            //更新
            if(cnt == 0) {
                if(r - l + 1 < minLen) {
                    minL = l;
                    minLen = r - l + 1;
                }
            }

            while(cnt == 0 && r >= l) {
                //去除s[l]
                hash[s.charAt(l) - 'a']++;
                //这种情况 去除s[l] 后 区间不包含 s[l]
                if(hash[s.charAt(l) - 'a'] == 1) cnt++;
                l++;
                //更新
                if(cnt == 0) {
                    if(r - l + 1 < minLen) {
                        minL = l;
                        minLen = r - l + 1;
                    }
                }
            }
            //继续向右
            r++;
        }
        System.out.println(s.substring(minL, minL + minLen));
    }
}
//滑动窗口
class Main_2_2 {
    static int cnt; //出现的字母种数
    static int[] hash;  //记录字母种类
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        hash = new int[26];
        String line = sc.nextLine();
        cnt = 0;
        for(char c : line.toCharArray()) {
            if(hash[c - 'a'] == 0) cnt++;
            hash[c - 'a'] = 1;
        }
        int L = cnt;    //至少cnt长，才可能包含所有出现类型的字母
        while(L <= line.length()) {
            if(check(line, L)) break;
            L++;
        }
    }
    static boolean check(String line, int L) {
        //副本
        int[] help = Arrays.copyOf(hash, 26);
        int count = cnt;
        //添加字母
        for(int i = 0; i < L; i++) {
            char c = line.charAt(i);
            help[c - 'a']--;
            if(help[c - 'a'] == 0) { //包含该字母
                count--;
            }
        }
        if(count == 0) {    //符合要求
            System.out.println(line.substring(0, L));
            return true;
        }
        //向右滑动
        for(int r = L; r < line.length(); r++) {
            //添加右端
            char c = line.charAt(r);
            help[c - 'a']--;
            if(help[c - 'a'] == 0) {
                count--;
            }
            //减去左端
            c = line.charAt(r - L);
            help[c - 'a']++;
            if(help[c - 'a'] == 1) {
                count++;
            }
            if(count == 0) { //符合要求
                System.out.println(line.substring(r - L + 1, r + 1));
                return true;
            }
        }

        return false;
    }
}
public class B_包含指定字母的最短子串 {

}
